package com.yuan.algorithms.面试题;

import java.io.*;
import java.nio.charset.StandardCharsets;
import java.util.*;

/**
 * 腾讯面试题
 * 有十亿条手机号的登录记录，服务器可用内存只有1G，请设计算法实现这10亿手机号的去重
 *
 * 解题思路：
 * 传统的数组循环去重或者利用Set集合去重，需要一次加载所有数据，一次性读取10亿数据使用String存储至少需要的JVM内存为10亿*(40+2*11)byte=57G，使用Long存储则需要7G内存，方案不可行。
 * 使用前缀树实现号码的储存与去重，手机号第一位均为1可以省去，树高10层，需要的内存为第1位是10bit，第2位要100bit，第10位10的10次方bit，共需1.5G
 * 使用BitMap：手机号第一位均为1可以省去，存储范围1000000000~9999999999共需要9999999999-1000000000(bit)=1.04G
 * BitMap优化：因为手机前3位为号段，只有有限的类型，可以将号码拆分为3位号段+8位号码的形式，BitMap只存储8位号码，号段使用Map映射，那么单个BitMap需要的内存为99999999-10000000(bit)=12M，创建50个号段，内存总花费12M*50=600M
 *
 * 读取数据：
 * Java中一个空 String 所占空间为：
 * 对象头（8 字节）+ 引用 (4 字节 )  + char 数组（16 字节）+ 1个 int（4字节）+ 1个long（8字节）= 40 字节。
 * String占用内存计算公式：40 + 2*n，n为字符串长度。
 * 按照公式，一次性读取10亿数据至少需要的内存为25G，所以要采用分批读取手机号数据的方式，一次读取500万条数据，大约消耗300M内存，10亿数据分200次读取
 *
 * 测试：
 * 运行时添加内存限制参数-Xms1G -Xmx1G，从文件中分批读取号码文件，程序进行去重，并输出去重后的全部手机号到一个新文件
 * @author YouYuan
 * @date 2022/3/22 17:02
 */
public class 十亿手机号去重 {


    //号段映射BitMap，初始化完成后占用空间600M
    public static final Map<String, BitSet> macMapping = new HashMap<>();
    //运营商启用的号段，用于初始化BitMap，如果数据中有其他号段也会自动初始化一个BitMap加入
    public static final String[] macs = {
            //移动号段
            "139", "138", "137", "136", "134", "135", "147", "150", "151", "152", "157", "158", "159", "172", "178", "182", "183", "184", "187", "188", "195", "197", "198",
            //联通号段
            "130", "131", "132", "140", "145", "146", "155", "156", "166", "185", "186", "175", "176", "196",
            //电信号段
            "133", "149", "153", "177", "173", "180", "181", "189", "191", "193", "199",
            //虚拟运营商号段
            "162", "165", "167", "170", "171"
    };

    //单次读取数据大小，一次读取500万数据，10亿数据分200次读取，每轮读取大约消耗300M内存
    private static final int readSize = 5000000;
    //bitmap长度，这里存储8位数字
    private static final int bitMapLength = 100000000;
    //读写文件的缓冲区大小10M
    private static final int ioBuffer = 1024*1024*10;

    static {
        /**
         * 根据号段创建每个号段的BitMap
         */
        for (int i = 0; i < macs.length; i++) {
            //初始化直接指定长度，避免不断扩容浪费性能
            macMapping.putIfAbsent(macs[i], new BitSet(bitMapLength));
        }
    }


    public static void main(String[] args) throws Exception {
//        Thread.sleep(600*1000);
        String filePath = buildMobileData();
        long s = System.currentTimeMillis();
        BufferedReader reader = new BufferedReader(new FileReader(filePath, StandardCharsets.UTF_8));
        List<String> mobileList = new ArrayList<>(readSize);
        readMobiles(reader, mobileList);
        int count = 0;//未去重的数据总量
        int uniqueCount = 0;//去重后的数据总量
        while (mobileList.size() > 0) {
            count += mobileList.size();
            //录入bitmap去重
            uniqueHandle(mobileList);
            System.out.println("当前已处理数据： "+ count);
//            Thread.sleep(60*1000);
            //读取下一批数据
            readMobiles(reader, mobileList);
        }
        uniqueCount = saveResult();
        System.out.printf("手机号数据总量：%d%n", count);
        System.out.printf("手机号去重后数据总量：%d%n", uniqueCount);
        long e = System.currentTimeMillis();
        System.out.println("去重排序总耗时：" + (e-s) + "(ms)");
    }

    private static int saveResult() throws IOException {
        int total = 0;
        boolean saveDisk = true;
        String filePath = "E:/Test/Data/十亿手机号去重结果.txt";
        File file = new File(filePath);
        BufferedWriter writer = null;
        if (file.exists()) {
            System.out.println("手机号去重数据已存在，不再重新生成文件...");
            saveDisk = false;
        } else {
            System.out.println("开始生成十亿手机号去重数据...");
            file.mkdirs();
            file.delete();
            file.createNewFile();
            writer = new BufferedWriter(new FileWriter(file), ioBuffer);
        }
        for (int i = 0; i < macs.length; i++) {
            String mac = macs[i];
            BitSet bitMap = macMapping.get(mac);
            int index = bitMap.nextSetBit(0);
            StringBuilder mobileBuilder = new StringBuilder();
            while (index >= 0) {
                mobileBuilder.append(mac);
                String numStr = "" + index;
                int numLen = numStr.length();
                while (numLen < 8) {
                    //补齐号码前几位是0的数据
                    mobileBuilder.append("0");
                    numLen++;
                }
                mobileBuilder.append(numStr);
                if (saveDisk) {
                    writer.write(mobileBuilder.append("\n").toString());
                }
                total++;
                //查找下一个数据
                index = bitMap.nextSetBit(index + 1);
                //重置mobileBuilder达到复用对象的效果，节省String对象创建的开销
                mobileBuilder.setLength(0);
            }
        }
        System.out.println("去重后数据保存完毕，文件路径: " + filePath);
        if (writer != null) {
            writer.flush();
            writer.close();
        }
        return total;
    }

    /**
     * 去重处理
     * @param mobileList
     */
    private static void uniqueHandle(List<String> mobileList) {
//        System.out.println("去重数据大小: "+ mobileList.size());
        for (int i = 0; i < mobileList.size(); i++) {
            String mobileStr = mobileList.get(i);
            String mac = mobileStr.substring(0, 3);
            String num = mobileStr.substring(3);
            //根据号段取对应的Bitmap，假如存在号段之外的数据，初始化一个新号段加入
            BitSet bitSet = macMapping.computeIfAbsent(mac, v -> new BitSet(bitMapLength));
            int index = Integer.parseInt(num);
//            System.out.println("i:" + i + ", mac:" + mac + ", index:" + index);
            bitSet.set(index);
        }
    }

    /**
     * 随机生成10亿条手机号数据，生成的文件大小约12G，共1060000000条随机号码数据
     */
    private static String buildMobileData() throws IOException {
        Random random = new Random();
        String filePath = "E:/Test/Data/十亿手机号.txt";
        File file = new File(filePath);
        if (file.exists()) {
            System.out.println("手机号数据已存在，不再生成随机数据...");
            return filePath;
        }
        System.out.println("开始生成十亿手机号数据...");
        file.mkdirs();
        file.delete();
        file.createNewFile();
        BufferedWriter writer = new BufferedWriter(new FileWriter(file, StandardCharsets.UTF_8), ioBuffer);
        for (int j = 1; j <= 20000000; j++) {
            int num = random.nextInt(99999999);
            String numStr = "" + num;
            while (numStr.length() < 8) {
                numStr = "0" + numStr;
            }
            for (int i = 0; i < macs.length; i++) {
                String randMobile = macs[i] + numStr;
                writer.write(randMobile + "\n");
            }
            if (j % 200000 == 0) {
                System.out.printf("生成数据进度：%d%%%n", j/200000);
            }
        }
        writer.flush();
        writer.close();
        System.out.println("十亿手机号数据生成完毕，文件路径：" + filePath);
        return filePath;
    }

    /**
     * 从文件流中分批次读取手机号数据，避免一次性读取爆内存
     * @param reader
     * @param mobileList
     * @throws IOException
     */
    private static void readMobiles(BufferedReader reader, List<String> mobileList) throws IOException {
        //读取数据之前清空列表历史数据
        mobileList.clear();
        //从文件中读取手机号数据，存入缓冲列表
        for (int j = 0; j < readSize; j++) {
            /**
             * //TODO 假如使用long存储手机号，内存占用会更小，但是需要额外的转换，使用CPU换内存 2022/3/30 -By YouYuan
             */
            String line = reader.readLine();
            if (line != null && line.length() > 1) {
                mobileList.add(line);
            }
        }
    }


}
